
<!DOCTYPE html>
<html lang="en" class="loading">
<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>什么是位运算？ - Hexo</title>
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate">
    <meta name="keywords" content="Fechin,"> 
    <meta name="description" content="位运算不再神秘计算机中的乘法就是用到了位运算的知识！例如15*13就会把13拆解成8+4+1 的形式 也就是 2的0次方 2的2次方和 2的三次方分别对应了 15&amp;lt;&amp;lt;0 (15左移0位）,"> 
    <meta name="author" content="John Doe"> 
    <link rel="alternative" href="atom.xml" title="Hexo" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon.png"> 
    
    <link rel="stylesheet" href="/css/diaspora.css">
	<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <script>
         (adsbygoogle = window.adsbygoogle || []).push({
              google_ad_client: "ca-pub-8691406134231910",
              enable_page_level_ads: true
         });
    </script>
    <script async custom-element="amp-auto-ads" src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js">
    </script>
</head>
</html>
<body class="loading">
    <span id="config-title" style="display:none">Hexo</span>
    <div id="loader"></div>
    <div id="single">
    <div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <a class="iconfont icon-home image-icon" href="javascript:;" data-url="http://h2440222798.gitee.io"></a>
    <div title="播放/暂停" class="iconfont icon-play"></div>
    <h3 class="subtitle">什么是位运算？</h3>
    <div class="social">
        <div>
            <div class="share">
                <a title="获取二维码" class="iconfont icon-scan" href="javascript:;"></a>
            </div>
            <div id="qr"></div>
        </div>
    </div>
    <div class="scrollbar"></div>
</div>

    <div class="section">
        <div class="article">
    <div class='main'>
        <h1 class="title">什么是位运算？</h1>
        <div class="stuff">
            <span>八月 20, 2019</span>
            
  <ul class="post-tags-list"><li class="post-tags-list-item"><a class="post-tags-list-link" href="/tags/位运算/">位运算</a></li></ul>


        </div>
        <div class="content markdown">
            <h1 id="位运算不再神秘"><a href="#位运算不再神秘" class="headerlink" title="位运算不再神秘"></a>位运算不再神秘</h1><h2 id="计算机中的乘法就是用到了位运算的知识！"><a href="#计算机中的乘法就是用到了位运算的知识！" class="headerlink" title="计算机中的乘法就是用到了位运算的知识！"></a>计算机中的乘法就是用到了位运算的知识！</h2><p>例如15*13<br>就会把13拆解成8+4+1 的形式 也就是 2的0次方 2的2次方和 2的三次方<br>分别对应了 15&lt;&lt;0 (15左移0位） + 15&lt;&lt;2 (15左移两位) + 15 &lt;&lt; 3 (15左移三位)的和<br>这样对于计算机来说，处理起来绝对相当简单！</p>
<h2 id="计算的减法其实就是加法"><a href="#计算的减法其实就是加法" class="headerlink" title="计算的减法其实就是加法"></a>计算的减法其实就是加法</h2><p>使用补码的方式进行运算，具体可以见计算机组成原理，设计的非常巧妙</p>
<h2 id="计算机中除法非常消耗时间"><a href="#计算机中除法非常消耗时间" class="headerlink" title="计算机中除法非常消耗时间"></a>计算机中除法非常消耗时间</h2><p>除法其实就是所有位数左移的过程，但是浮点数的除法，小数的处理真的非常耗时间。</p>
<hr>
<h1 id="基本的位运算符号"><a href="#基本的位运算符号" class="headerlink" title="基本的位运算符号"></a>基本的位运算符号</h1><table>
<thead>
<tr>
<th>含义</th>
<th>运算符</th>
<th>例子</th>
</tr>
</thead>
<tbody><tr>
<td>左移</td>
<td>&lt;&lt;</td>
<td>0011 =&gt; 0110</td>
</tr>
<tr>
<td>右移</td>
<td>&gt;&gt;</td>
<td>0110 =&gt; 0011</td>
</tr>
<tr>
<td>按位或</td>
<td>一个竖线</td>
<td>0011 竖线 1011 =&gt; 1011</td>
</tr>
<tr>
<td>按位与</td>
<td>&amp;</td>
<td>0011 &amp; 1011 =&gt; 0011</td>
</tr>
<tr>
<td>按位取反</td>
<td>~</td>
<td>0011 =&gt; 1100</td>
</tr>
<tr>
<td>按位异或（相同0不同1）</td>
<td>^</td>
<td>0011 ^ 1011 =&gt; 1000</td>
</tr>
<tr>
<td>—</td>
<td></td>
<td></td>
</tr>
</tbody></table>
<h1 id="https-www-acwing-com-problem-content-91-标准的快速幂"><a href="#https-www-acwing-com-problem-content-91-标准的快速幂" class="headerlink" title="https://www.acwing.com/problem/content/91/ 标准的快速幂"></a><a href="https://www.acwing.com/problem/content/91/" target="_blank" rel="noopener">https://www.acwing.com/problem/content/91/</a> 标准的快速幂</h1><p>这是一个问a的b次方 模 p 的问题<br>由于数值比较大 计算时间也比较长 所以最好的方法就是用位运算来做</p>
<p>这个是一个快速幂的模板题目：<br>快速幂的核心就是 a的b次方其实就是 把 b 拆分成2的所有幂次 然后再相乘；这样对于一个2的15次方的数最多也就是算15次，非常省时间<br>15 的 13 次方 = 15左移0位 * 15 左移2位 * 15左移 3 位的相乘</p>
<p>所以说，位运算是对应了计算机本身的东西，比较适合计算机去做。</p>
<p>快速幂模板</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">import java.util.Scanner;</span><br><span class="line">public class 快速幂 &#123;</span><br><span class="line">	public static long  fastmimi(long a, long b , long p)&#123;</span><br><span class="line">		 long ans = 1%p;</span><br><span class="line">		while(b &gt; 0)&#123;</span><br><span class="line">			long tmp = b &amp; 1;</span><br><span class="line">			if(tmp == 1)&#123;</span><br><span class="line">				ans = (long)ans*a%p;</span><br><span class="line">			&#125;</span><br><span class="line">			a = (a*(long)a%p);</span><br><span class="line">			b &gt;&gt;= 1;</span><br><span class="line">		&#125;</span><br><span class="line">		return ans;</span><br><span class="line">	&#125;</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		Scanner in = new Scanner(System.in);</span><br><span class="line">		long a = in.nextLong();</span><br><span class="line">		long b = in.nextLong();</span><br><span class="line">		long p = in.nextLong();</span><br><span class="line">		long ans = fastmimi(a, b, p);</span><br><span class="line">		System.out.println(ans);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<hr>
<h1 id="https-www-acwing-com-problem-content-description-92-乘法的缘由"><a href="#https-www-acwing-com-problem-content-description-92-乘法的缘由" class="headerlink" title="https://www.acwing.com/problem/content/description/92/  乘法的缘由"></a><a href="https://www.acwing.com/problem/content/description/92/" target="_blank" rel="noopener">https://www.acwing.com/problem/content/description/92/</a>  乘法的缘由</h1><p>如何将其应用的乘法上面，记住比价重要的一点就是 对于a的处理上，一定记得乘法是加法的翻倍，幂次是乘法的翻倍<br>然后对于答案也是对于结果的相加</p>
<h2 id="前面已经介绍过了"><a href="#前面已经介绍过了" class="headerlink" title="前面已经介绍过了"></a>前面已经介绍过了</h2><h1 id="位运算一个比较高级的应用就是状态压缩DP"><a href="#位运算一个比较高级的应用就是状态压缩DP" class="headerlink" title="位运算一个比较高级的应用就是状态压缩DP"></a>位运算一个比较高级的应用就是状态压缩DP</h1><p>哈密顿路径就是指 从一个点走到另一个点，经过所有的中间节点，最短的路径<br>(到时候再写吧)</p>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls" data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
                <ul id="audio-list" style="display:none">
                    
                        
                            <li title='0' data-url='http://link.hhtjim.com/163/425570952.mp3'></li>
                        
                    
                        
                            <li title='1' data-url='http://link.hhtjim.com/163/425570952.mp3'></li>
                        
                    
                </ul>
            
        </div>
        
    <div id='gitalk-container' class="comment link"
		data-enable='false'
        data-ae='false'
        data-ci=''
        data-cs=''
        data-r=''
        data-o=''
        data-a=''
        data-d='false'
    >查看评论</div>


    </div>
    
</div>


    </div>
</div>
</body>

<script src="//lib.baomitu.com/jquery/1.8.3/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/typed.js"></script>
<script src="/js/diaspora.js"></script>
<link rel="stylesheet" href="/photoswipe/photoswipe.css">
<link rel="stylesheet" href="/photoswipe/default-skin/default-skin.css">
<script src="/photoswipe/photoswipe.min.js"></script>
<script src="/photoswipe/photoswipe-ui-default.min.js"></script>

<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>






</html>
